package 分割回文串;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: AirMan
 * @date: 2025/4/14 20:32
 * @description:
 */
public class Solution2 {
    public List<List<String>> partition(String s) {
        // 切割问题类似组合问题
        // 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段.....
        // 回溯的参数：s, startIndex, path, result
        // 回溯的返回值：void
        // 回溯的终止条件：切割的不是回文 或者 串s被完全切割(startIndex > length)
        // 单层回溯的逻辑：
        // 横向通过for循环遍历串s,每次的起始索引索要加1，这样就避免了字串重复，截取的范围是 startIndex --> i
        // 纵向遍历后续的字串，每递归一个树的分支就是代表截取的字串是不同的，startIndex --> i 即截取的分支
        // 如果他是回文串，那么下一次回文串的开始位置是 i + 1
        /*
         切割问题可以抽象为组合问题：
         如何模拟那些切割线？？？？
         切割问题中递归如何终止？？？？
         在递归循环中如何截取子串？？？？
         如何判断回文？？？？
        */
        length = s.length();
        computePalindrome(s);
        backtarcking(s, 0);
        return result;
    }

    private List<List<String>> result = new ArrayList<>();
    private List<String> path = new ArrayList<>();
    private int length;
    boolean[][] dp;

    public void backtarcking(String s, int startIndex) {
        if (startIndex >= length) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = startIndex; i < length; i++) {
            if (dp[startIndex][i]) {
                // 当前串是回文串，加入到 path 中, 左闭右开
                // 左闭右开
                path.add(s.substring(startIndex, i + 1));
                // 递归
                backtarcking(s, i + 1);
            } else {
                continue;
            }
            // 回溯
            path.remove(path.size() - 1);
        }
    }

    public void computePalindrome(String s) {
        dp = new boolean[length][length];
        for (int i = 0; i < length; i++) {
            dp[i][i] = true;
        }
        for (int i = length - 1; i >= 0; i--) {
            for (int j = i + 1; j < length; j++) {  // 从 i 之后的字符开始遍历
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i == 1) {
                        dp[i][j] = true;  // 两个字符相等时，直接是回文
                    } else if (dp[i + 1][j - 1]) {
                        dp[i][j] = true;  // 如果中间的子串是回文，则当前子串也是回文
                    }
                }
            }
        }
    }
}
